package th.android.sudoku;


import java.util.ArrayList;
import java.util.List;

/**
 * @author me_touch
 * @version V1.0.0 21-3-10
 */
public class Sudo {
    
    private final static int N = 9;

    private int[][] mOriginSudoKu;
    private int[][] mSolvedSudoku;

    private int mSolutionCount;
    private int[] mRows = new int[9];
    private int[] mColumns = new int[9];
    private int[] mBoxes = new int[9];
    private List<int[]> mSpaces = new ArrayList<>();

    public Sudo() {
        mOriginSudoKu = new int[N][N];
        mSolvedSudoku = new int[N][N];
    }

    public Sudo(int[] arr) {
        this();
        if (arr.length != N * N) {
            initError();
        }
        for (int i = 0; i < N; i ++) {
            for (int j = 0; j < N; j++) {
                int num = arr[i * N + j];
                if (num >= 0 && num <= N) {
                    mOriginSudoKu[i][j] = num;

                } else {
                    initError();
                }
            }
        }
    }

    public Sudo(int[][] arr) {
        this();
        for (int i = 0; i < N; i++) {
            System.arraycopy(arr[i], 0, mOriginSudoKu[i], 0, N);
            System.arraycopy(arr[i], 0, mSolvedSudoku[i], 0, N);
        }
    }

    public boolean isLegal() {
        final int[][] row = new int[N][N];
        final int[][] column = new int[N][N];
        final int[][] box = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                final int num = mOriginSudoKu[i][j] - 1;
                if (num >= 0) {
                    row[i][num] += 1;
                    column[j][num] += 1;
                    final int boxIndex = (i / 3) * 3 + j / 3;
                    box[boxIndex][num] += 1;
                    if (row[i][num] > 1 || column[j][num] > 1 || box[boxIndex][num] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public boolean isCompleted() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                final int num = mSolvedSudoku[i][j] - 1;
                if (num == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    public int[][] getSolvedSudoku() {
        autoFill();
        return mSolvedSudoku;
    }

    public int[][] getOriginSudoKu() {
        return mOriginSudoKu;
    }

    public boolean isSolutionUnique() {
        solve(2);
        return mSolutionCount < 2;
    }

    private void autoFill() {
        if (!isCompleted()) {
            solve(1);
        }
    }

    private void solve(int solutionCount) {
        reset();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (mSolvedSudoku[i][j] != 0) {
                    int index = mSolvedSudoku[i][j] - 1;
                    bitTransform(i, j, index);
                }
            }
        }
        while (true) {
            boolean modified = false;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (mSolvedSudoku[i][j] == 0) {
                        int mask = ~(mRows[i] | mColumns[j] | mBoxes[i / 3 * 3 + j / 3]) & 0x1ff;
                        if ((mask & (mask - 1)) == 0) {
                            int digit = Integer.bitCount(mask - 1);
                            bitTransform(i, j, digit);
                            mSolvedSudoku[i][j] = digit + 1;
                            modified = true;
                        }
                    }
                }
            }
            if (!modified) {
                break;
            }
        }
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (mSolvedSudoku[i][j] == 0) {
                    mSpaces.add(new int[]{i, j});
                }
            }
        }
        dfs(0, solutionCount);
    }

    private void dfs(int pos, int maxSolutionCount) {
        if (pos == mSpaces.size()) {
            mSolutionCount++;
            return;
        }
        int[] space = mSpaces.get(pos);
        int i = space[0], j = space[1];
        int mask = ~(mRows[i] | mColumns[j] | mBoxes[i / 3 * 3 + j / 3]) & 0x1ff;
        for (; mask != 0 && mSolutionCount < maxSolutionCount; mask &= (mask - 1)) {
            int digitMask = mask & (-mask);
            int digit = Integer.bitCount(digitMask - 1);
            bitTransform(i, j, digit);
            mSolvedSudoku[i][j] = digit + 1;
            dfs(pos + 1, maxSolutionCount);
            bitTransform(i, j, digit);
        }
    }

    private void bitTransform(int i, int j, int index) {
        int temp = 1 << index;
        mRows[i] ^= temp;
        mColumns[j] ^= temp;
        int pos = i / 3 * 3 + j / 3;
        mBoxes[pos] ^= temp;
    }

    private void reset() {
        mSolutionCount = 0;
        for (int i = 0; i < N; i++) {
            System.arraycopy(mOriginSudoKu[i], 0, mSolvedSudoku[i], 0, N);
            mRows[i] = 0;
            mColumns[i] = 0;
            mBoxes[i] = 0;
        }
        mSpaces.clear();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                builder.append(mOriginSudoKu[i][j]);
                if (j != 8) {
                    builder.append(',');
                } else {
                    builder.append('\n');
                }
            }
        }
        return builder.toString();
    }

    private void initError() {
        throw new IllegalArgumentException("can`t be converted to a Sudo");
    }

    public static void main(String[] args) {
        int[] arr = {
                3, 0, 0, 8, 9, 0, 0, 0, 4,
                0, 0, 0, 0, 0, 1, 0, 0, 0,
                0, 9, 0, 6, 2, 0, 5, 0, 0,
                4, 0, 0, 1, 0, 0, 0, 3, 0,
                0, 0, 0, 0, 8, 6, 0, 0, 0,
                0, 1, 6, 0, 0, 9, 0, 7, 0,
                0, 5, 0, 0, 0, 0, 0, 0, 0,
                9, 0, 2, 0, 0, 0, 0, 4, 7,
                0, 4, 0, 9, 0, 3, 0, 0, 1
        };
        Sudo sudo = new Sudo(arr);
        System.out.println(sudo.isSolutionUnique());
    }
}
